The present invention relates generally to communication networks, and more specifically, to network traffic matrix analysis.
A traffic matrix is the set of bandwidths of all end-to-end flows across a network. The information provided by a traffic matrix is critical in a number of network planning tasks. While some interior routing technologies such as MPLS-TE allow fairly convenient collection of the traffic matrix, many operators of large networks run OSPF (Open Shortest Path First) or IS-IS (Intermediate System to Intermediate System) as the core interior routing protocol. In such a context, a complete traffic matrix is not readily available. In practice, information about the traffic matrix must be pieced together from a number of different sources.
Another option for collection of the traffic matrix is to use Cisco IOS NetFlow (available from Cisco Systems, Inc. of San Jose, Calif.), in which routers collect flow information and export raw or aggregated data. NetFlow software for traffic monitoring or hardware traffic probes can be installed around the perimeter of the core and provide very detailed traffic matrix information. However, an approach based purely on NetFlow or hardware probing is not appropriate for all network operators.
Traffic matrix analysis can be performed using observations of traffic at a local device level, such as link loads. Traffic matrix inference is one traffic matrix analysis technique used for obtaining information about the traffic matrix. Traffic matrix inference is the construction of a logical system which captures what is known about the traffic matrix from observation and routing data. Traffic matrix inference is used to describe inference techniques that are applied when the network operator has only a partial view of the traffic traversing the network, but wishes to extend this partial view to a more complete view. Using certain computational techniques, sound inferences can be made about the traffic matrix. One way to do traffic inference is to construct a linear constraint system to model the topology, routing, and local traffic observations. The true traffic matrix must be consistent with the topology, routing, and traffic observations and must therefore satisfy the constraints. Using linear constraint solvers one can therefore reason about the true traffic matrix.
An example of traffic matrix inference is described in U.S. Patent Publication No. 2004/0218529, entitled “Traffic Flow Optimisation System”, published Nov. 4, 2004, which is incorporated herein by reference in its entirety. The system uses linear programming solvers to construct a constraint system (referred to as TFM (Traffic Flow Model)) from local link load traffic observations.
U.S. Pat. Nos. 6,061,331 and 6,560,204 also use linear programming to perform traffic matrix analysis from local observations and routing data. The method of U.S. Pat. No. 6,061,331 uses measurements made over multiple disjoint time periods of traffic coming into the network at each node and measurements of traffic on each link. The method subsequently uses these measurements to set up linear programming problems for finding an approximate source-destination traffic matrix that optimally fits the measured data. The model used in the U.S. Pat. No. 6,560,204 is not tractable enough to be solved directly and requires iterative fitting. The methods described above are all designed for use with link measurements.
Traffic matrix inference can be used to compute maximum and minimum bounds for the bandwidth of each flow. Due to the fact that the constraint system is usually very under constrained, these bounds normally leave a very wide margin of uncertainty for the actual value of each flow. Traffic matrix inference is therefore often combined with other traffic matrix analysis techniques, such as traffic matrix estimation, in which heuristics can be used to identify a definite traffic matrix that is consistent with the constraint system and is a reasonable approximation of the actual, unknown traffic matrix.
Traffic matrix estimation consists of generating concrete estimates for the elements in the traffic matrix. A conventional estimation heuristic, known as the “gravity approach”, relies on local observations about ingress and egress traffic at each edge node. These observations are combined with the “gravity assumption” and the constraint system to give definite values for the matrix (see, for example, “Fast Accurate Computation of Large-Scale IP Traffic Matrices from Link Loads”, Yin Zhang et al., ACM SIGMETRICS, June 2003).
As described above, conventional systems perform traffic matrix inference using link observations. Furthermore, traffic matrix estimation heuristics such as the gravity approach only use traffic observations at the edge nodes. These narrow sets of observations provide only limited accuracies in traffic matrix analysis.
Corresponding reference characters indicate corresponding parts throughout the several views of the drawings.